Search Results

Documents authored by Hellouin de Menibus, Benjamin

Found 2 Possible Name Variants:

Hellouin de Ménibus, Benjamin

Document
DOI: 10.4230/LIPIcs.STACS.2022.19
The Aperiodic Domino Problem in Higher Dimension

Authors: Antonin Callard and Benjamin Hellouin de Menibus

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
The classical Domino problem asks whether there exists a tiling in which none of the forbidden patterns given as input appear. In this paper, we consider the aperiodic version of the Domino problem: given as input a family of forbidden patterns, does it allow an aperiodic tiling? The input may correspond to a subshift of finite type, a sofic subshift or an effective subshift. [Grandjean et al., 2018] proved that this problem is co-recursively enumerable (Π₀¹-complete) in dimension 2 for geometrical reasons. We show that it is much harder, namely analytic (Σ₁¹-complete), in higher dimension: d ≥ 4 in the finite type case, d ≥ 3 for sofic and effective subshifts. The reduction uses a subshift embedding universal computation and two additional dimensions to control periodicity. This complexity jump is surprising for two reasons: first, it separates 2- and 3-dimensional subshifts, whereas most subshift properties are the same in dimension 2 and higher; second, it is unexpectedly large.
Cite as

Antonin Callard and Benjamin Hellouin de Menibus. The Aperiodic Domino Problem in Higher Dimension. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{callard_et_al:LIPIcs.STACS.2022.19,
  author =	{Callard, Antonin and Hellouin de Menibus, Benjamin},
  title =	{{The Aperiodic Domino Problem in Higher Dimension}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{19:1--19:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.19},
  URN =		{urn:nbn:de:0030-drops-158296},
  doi =		{10.4230/LIPIcs.STACS.2022.19},
  annote =	{Keywords: Subshift, periodicity, aperiodicity, domino problem, subshift of finite type, sofic subshift, effective subshift, tilings, computability}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.128
Aperiodic Points in Z²-subshifts

Authors: Anael Grandjean, Benjamin Hellouin de Menibus, and Pascal Vanier

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We consider the structure of aperiodic points in Z^2-subshifts, and in particular the positions at which they fail to be periodic. We prove that if a Z^2-subshift contains points whose smallest period is arbitrarily large, then it contains an aperiodic point. This lets us characterise the computational difficulty of deciding if an Z^2-subshift of finite type contains an aperiodic point. Another consequence is that Z^2-subshifts with no aperiodic point have a very strong dynamical structure and are almost topologically conjugate to some Z-subshift. Finally, we use this result to characterize sets of possible slopes of periodicity for Z^3-subshifts of finite type.
Cite as

Anael Grandjean, Benjamin Hellouin de Menibus, and Pascal Vanier. Aperiodic Points in Z²-subshifts. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 128:1-128:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{grandjean_et_al:LIPIcs.ICALP.2018.128,
  author =	{Grandjean, Anael and Hellouin de Menibus, Benjamin and Vanier, Pascal},
  title =	{{Aperiodic Points in Z²-subshifts}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{128:1--128:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.128},
  URN =		{urn:nbn:de:0030-drops-91323},
  doi =		{10.4230/LIPIcs.ICALP.2018.128},
  annote =	{Keywords: Subshifts of finite type, Wang tiles, periodicity, aperiodicity, computability, tilings}
}
Document
DOI: 10.4230/LIPIcs.STACS.2015.262
Construction of mu-Limit Sets of Two-dimensional Cellular Automata

Authors: Martin Delacourt and Benjamin Hellouin de Ménibus

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
We prove a characterisation of \mu-limit sets of two-dimensional cellular automata, extending existing results in the one-dimensional case. This sets describe the typical asymptotic behaviour of the cellular automaton, getting rid of exceptional cases, when starting from the uniform measure.
Cite as

Martin Delacourt and Benjamin Hellouin de Ménibus. Construction of mu-Limit Sets of Two-dimensional Cellular Automata. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 262-274, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{delacourt_et_al:LIPIcs.STACS.2015.262,
  author =	{Delacourt, Martin and Hellouin de M\'{e}nibus, Benjamin},
  title =	{{Construction of mu-Limit Sets of Two-dimensional Cellular Automata}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{262--274},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.262},
  URN =		{urn:nbn:de:0030-drops-49197},
  doi =		{10.4230/LIPIcs.STACS.2015.262},
  annote =	{Keywords: cellular automata, dynamical systems, mu-limit sets, subshifts, measures}
}

Hellouin de Menibus, Benjamin

Document
DOI: 10.4230/LIPIcs.STACS.2022.19
The Aperiodic Domino Problem in Higher Dimension

Authors: Antonin Callard and Benjamin Hellouin de Menibus

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
The classical Domino problem asks whether there exists a tiling in which none of the forbidden patterns given as input appear. In this paper, we consider the aperiodic version of the Domino problem: given as input a family of forbidden patterns, does it allow an aperiodic tiling? The input may correspond to a subshift of finite type, a sofic subshift or an effective subshift. [Grandjean et al., 2018] proved that this problem is co-recursively enumerable (Π₀¹-complete) in dimension 2 for geometrical reasons. We show that it is much harder, namely analytic (Σ₁¹-complete), in higher dimension: d ≥ 4 in the finite type case, d ≥ 3 for sofic and effective subshifts. The reduction uses a subshift embedding universal computation and two additional dimensions to control periodicity. This complexity jump is surprising for two reasons: first, it separates 2- and 3-dimensional subshifts, whereas most subshift properties are the same in dimension 2 and higher; second, it is unexpectedly large.
Cite as

Antonin Callard and Benjamin Hellouin de Menibus. The Aperiodic Domino Problem in Higher Dimension. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{callard_et_al:LIPIcs.STACS.2022.19,
  author =	{Callard, Antonin and Hellouin de Menibus, Benjamin},
  title =	{{The Aperiodic Domino Problem in Higher Dimension}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{19:1--19:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.19},
  URN =		{urn:nbn:de:0030-drops-158296},
  doi =		{10.4230/LIPIcs.STACS.2022.19},
  annote =	{Keywords: Subshift, periodicity, aperiodicity, domino problem, subshift of finite type, sofic subshift, effective subshift, tilings, computability}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.128
Aperiodic Points in Z²-subshifts

Authors: Anael Grandjean, Benjamin Hellouin de Menibus, and Pascal Vanier

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We consider the structure of aperiodic points in Z^2-subshifts, and in particular the positions at which they fail to be periodic. We prove that if a Z^2-subshift contains points whose smallest period is arbitrarily large, then it contains an aperiodic point. This lets us characterise the computational difficulty of deciding if an Z^2-subshift of finite type contains an aperiodic point. Another consequence is that Z^2-subshifts with no aperiodic point have a very strong dynamical structure and are almost topologically conjugate to some Z-subshift. Finally, we use this result to characterize sets of possible slopes of periodicity for Z^3-subshifts of finite type.
Cite as

Anael Grandjean, Benjamin Hellouin de Menibus, and Pascal Vanier. Aperiodic Points in Z²-subshifts. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 128:1-128:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{grandjean_et_al:LIPIcs.ICALP.2018.128,
  author =	{Grandjean, Anael and Hellouin de Menibus, Benjamin and Vanier, Pascal},
  title =	{{Aperiodic Points in Z²-subshifts}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{128:1--128:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.128},
  URN =		{urn:nbn:de:0030-drops-91323},
  doi =		{10.4230/LIPIcs.ICALP.2018.128},
  annote =	{Keywords: Subshifts of finite type, Wang tiles, periodicity, aperiodicity, computability, tilings}
}
Document
DOI: 10.4230/LIPIcs.STACS.2015.262
Construction of mu-Limit Sets of Two-dimensional Cellular Automata

Authors: Martin Delacourt and Benjamin Hellouin de Ménibus

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
We prove a characterisation of \mu-limit sets of two-dimensional cellular automata, extending existing results in the one-dimensional case. This sets describe the typical asymptotic behaviour of the cellular automaton, getting rid of exceptional cases, when starting from the uniform measure.
Cite as

Martin Delacourt and Benjamin Hellouin de Ménibus. Construction of mu-Limit Sets of Two-dimensional Cellular Automata. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 262-274, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{delacourt_et_al:LIPIcs.STACS.2015.262,
  author =	{Delacourt, Martin and Hellouin de M\'{e}nibus, Benjamin},
  title =	{{Construction of mu-Limit Sets of Two-dimensional Cellular Automata}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{262--274},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.262},
  URN =		{urn:nbn:de:0030-drops-49197},
  doi =		{10.4230/LIPIcs.STACS.2015.262},
  annote =	{Keywords: cellular automata, dynamical systems, mu-limit sets, subshifts, measures}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact